#include <iostream>

namespace me
{
    template <typename T>
    struct bs_node
    {
        T _key;
        bs_node* _left;
        bs_node* _right;

        bs_node(const T& val)
            :_key(val),
            _left(nullptr),
            _right(nullptr)
        {}
    };

    template <typename T>
    class bstree
    {
        using node = bs_node<T>;
    public:
        bstree():_root(nullptr) {}

        ~bstree()
        {
            destroy(_root);
            _root = nullptr;
        }

        bstree(const bstree& bt)
        {
            _root = copy(bt._root);
        }

        node* copy(const node* root)
        {
            if(root == nullptr) return nullptr;
            node* newnode = new node(root->_key);
            newnode->_left = copy(root->_left);
            newnode->_right = copy(root->_right);

            return newnode;
        }

        bstree& operator=(bstree bt)
        {
            std::swap(_root, bt._root);
            return *this;
        }

        bool insert(const T& val)
        {
            if(_root == nullptr) {
                // 搜索树为空，直接将新节点赋值给根
                node* newnode = new node(val);
                _root = newnode;
            }else {
                // 搜索树不为空，开始比较每一个位置，找到符合要求的节点
                node* cur = _root;
                node* prev = nullptr; //记录目标位置的父节点
                while(cur) {
                    if(val < cur->_key) {
                        prev = cur;
                        cur = cur->left;
                    }else if(val > cur->_key) {
                        prev = cur;
                        cur = cur->right;
                    }else {
                        return false;// 不允许冗余   
                    }
                }

                node* newnode = new node(val);
                if(newnode->_key < prev->_key) {
                    prev->_left = newnode;
                }else {
                    prev->_right = newnode;
                }
            }
            return true;
        }

        // 中序遍历
        void inorder()
        {
            _inorder(_root);
        }

        // 查找
        bool find(const T& val)
        {
            node* cur = _root;
            while(cur) {
                if(val < cur->_key) {
                    cur = cur->_left;
                }else if(val > cur->_key) {
                    cur = cur->_right;
                }else {
                    return true;
                }
            }
            return false;
        }

        bool erase(const T& val)
        {
            // 1.先查找指定元素是否存储
            node* cur = _root;
            node* prev = nullptr;
            while(cur) {
                if(val < cur->_key) {
                    prev = cur;
                    cur = cur->_left;
                }else if(val > cur->_key) {
                    prev = cur;
                    cur = cur->_right;
                }else {
                    // 已经找到指定元素
                    // cur指向待删除的数据，prev是cur的父节点

                    // 左子树为空
                    if(cur->_left == nullptr) {
                        if(cur == _root) {//删除根节点
                            _root = cur->_right;
                        }else {
                            if(cur == prev->_left) {
                                prev->_left = cur->_right;
                            }else {
                                prev->_right = cur->_right;
                            }
                        }
                        delete cur;
                        cur = nullptr;
                    }else if(cur->_right == nullptr) {//右子树为空
                        if(cur == _root) {
                            _root = cur->_left;
                        }else{
                            if(cur == prev->_left) {
                                prev->_left = cur->_left;
                            }else {
                                prev->_right = cur->_left;
                            }
                        }
                        delete cur;
                        cur = nullptr;
                    }else {
                        // 左右子树都不为空
                        // 法1：找到指定元素的左子树的最右节点，交换值后，删除最右节点
                        // 法2：找到指定元素的右子树的最左节点，交换值后，删除最左节点

                        // 1.找左子树的最右节点
                        node* replace = cur->_left; // 左子树的根
                        node* replaceParent = cur; // 最右节点的父亲
                        while(replace->_right) {
                            replaceParent = replace;
                            replace = replace->_right;
                        }

                        // 2.此时replace指向最右节点， parent是它的父亲
                        // 交换值
                        cur->_key = replace->_key;

                        // 3.删除replace，将replace的左子树连接到parent对应的一侧
                        if(replace == replaceParent->_left) {
                            replaceParent->_left = replace->_left;
                        }else {
                            replaceParent->_right = replace->_left;
                        }

                        // 4.删除replace节点
                        delete replace;
                        replace = nullptr;
                    }
                    return true;
                }
            }
            return false;
        }
    private:
        // 后序析构搜索树的所有节点
        void destroy(node* root)
        {
            if(root == nullptr) return;
            destroy(root->_left);
            destroy(root->_right);
            delete root;
        }

        void _inorder(node* root)
        {
            if(root == nullptr) return;
            _inorder(root->_left);
            std::cout << root->_key << " ";
            _inorder(root->_right);
        }
        node* _root;
    };
}

int main()
{
    return 0;
}